package problem10_Regular_Expression_Matching;
/**
 * @see <a href="http://cwind.iteye.com/blog/2228723" /> 
 */
public class Solution {
	public boolean isMatch(String s, String p) {
		boolean matches[] =new boolean[s.length()+1];
		matches[s.length()]=true;
		for(int i=p.length()-1;i>=0;i--){
			if(p.charAt(i)=='*'){
				for(int j=s.length()-1;j>=0;j--){
					//matches[j]|| for aab c*a*b
					matches[j]=matches[j]||matches[j+1]&&(s.charAt(j)==p.charAt(i-1)||p.charAt(i-1)=='.');
				}
				i--;
			}else{
				for(int j=0;j<s.length();j++){
					matches[j]=matches[j+1]&&(s.charAt(j)==p.charAt(i)||p.charAt(i)=='.');
				}
				//for aaa .*c
				matches[s.length()]=false;
			}
		}
		return matches[0];
	}

	public static void main(String[] args) {
		System.out.println(new Solution().isMatch("aab", "c*a*b"));
		System.out.println(new Solution().isMatch("aaa", "aa"));
		System.out.println(new Solution().isMatch("ab", ".*c"));
	}
}
